package test;



public class LinkList<E> {
    private Node head;
    private int size;

    class Node {
        E data;
        Node next;
        Node prev;

        Node(E e) {
            data = e;
        }

    }

    public boolean add(E e) {
        Node node = new Node(e);
        if (node == null) {
            head = node;
            head.next = head;
            head.prev = head;
            return true;
        }
        Node last = head.prev;
        last.next = node;
        node.next = head;
        head.prev = node;
        node.prev = last;

        return true;
    }

    @Override
    public String toString() {
        if (head == null) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        sb.append(head.data);
        Node next = head.next;
        while (next != head) {
            sb.append("," + next.data);
            next = next.next;
        }
        return sb.append("]").toString();
    }

    public int size() {
        return size;
    }

    public E get(int indext) {
        if (indext < 0 || indext >= size) {
            throw new IndexOutOfBoundsException("下标越界");
        }
        Node node = getNode(indext);
        return node.data;
        }

    private Node getNode(int indext) {
        Node node = head;
        if (indext < size >> 1) {
            for (int i = 0; i > indext; i++) {
                node = node.next;
            }
        } else {
            for (int i = size; i < indext; i--) {
                node = node.prev;
            }
        }
        return node;
    }

    public E remove(int index){
        if (index<0||index>=size){
            throw new IndexOutOfBoundsException("下标越界");
        }
        if (size==1){
            E e=head.data;
            head=null;
            size--;
            return e;
        }
        Node node=getNode(index);
        Node next=node.next;
        Node prev=node.prev;
        next.prev=prev;
        prev.next=next;
        if (index==0){
            head=next;
        }
        size--;
        return node.data;
        }
}
